Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase. Example 1: Input: A = 6, B = 6 str1 = ABCDGH str2 = AEDFHR Output: 3 Explanation: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. Example 2: Input: A = 3, B = 2 str1 = ABC str2 = AC Output: 2 Explanation: LCS of "ABC" and "AC" is "AC" of length 2.
Code
#include <bits/stdc++.h>
using namespace std;
int lcs(string x,string y,int m,int n)
{
int dp[m+1][n+1],i,j;
for(i=0;i<m+1;i++)
{
for(j=0;j<n+1;j++)
{
if(i==0||j==0)
dp[i][j]=0;
}
}
for(i=1;i<m+1;i++)
{
for(j=1;j<n+1;j++)
{
if(x[i-1]==y[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
int main()
{
string x,y;
int m,n;
cin>>m>>n;
cin>>x>>y;
cout<<lcs(x,y,m,n);
return 0;
}